#include <dbg.h>

#include <cassert>
using namespace std;

class Solution {
public:
    string shortestBeautifulSubstring(string s, int k) {
        if (count(s.begin(), s.end(), '1') < k) {  // 没有k个1
            return "";
        }
        string res = s;
        int n = s.size();
        int cnt1 = 0;
        int left = 0;
        for (int right = 0; right < n; right++) {
            if (s[right] == '1') {
                ++cnt1;
            }
            while (cnt1 > k ||
                   s[left] == '0') {   // 左端点不是1 或者 1的个数大于k
                if (s[left] == '1') {  // 左端点是1 则 1的个数减一
                    --cnt1;
                }
                ++left;  // 左端点右移
            }
            if (cnt1 == k) {  // 1的个数等于k
                string tmp = s.substr(left, right - left + 1);
                if (tmp.size() < res.size() ||
                    (tmp.size() == res.size() && tmp < res)) {
                    res = tmp;
                }
            }
        }
        return res;
    }
};

int main() {
    Solution s;

    assert(s.shortestBeautifulSubstring("100011001", 3) == "11001");
    assert(s.shortestBeautifulSubstring("1011", 2) == "11");

    return 0;
}